package com.lee.algorithm.tree;

import com.lee.algorithm.tree.struct.TreeNode;

/***
 * @description: 满二叉树：每一层的节点数都达到最大值
 *      最大深度：l，节点数：N
 *      N = 2的l次方 - 1 -> N = 1 << l - 1
 * @author : 青石路
 * @date: 2021/12/10 21:32
 */
public class FullBinaryTree {

    public static void main(String[] args) {
        System.out.println(1 << 4);
    }

    /**
     * 判断一颗二叉树是否是完全二叉树
     *
     * 树形递归
     *      向左树要信息：1.深度，2.节点数
     *      向右树要信息：1.深度，2.节点数
     *      确立信息结构体：ReturnData
     *
     * @param root
     * @return
     */
    public static boolean isFbt(TreeNode<String> root) {
        ReturnData returnData = judgeFbt(root);
        return returnData.nodes == (1 << returnData.depth - 1);
    }

    /**
     * 信息结构体
     */
    static class ReturnData {
        int depth;
        int nodes;

        ReturnData (int depth, int nodes) {
            this.depth = depth;
            this.nodes = nodes;
        }
    }

    public static ReturnData judgeFbt(TreeNode<String> node) {
        if (node == null) {
            return new ReturnData(0, 0);
        }

        ReturnData leftData = judgeFbt(node.left);
        ReturnData rightData = judgeFbt(node.right);

        int nodes = leftData.nodes + rightData.nodes + 1;
        int depth = Math.max(leftData.depth, rightData.depth) + 1;
        return new ReturnData(depth, nodes);
    }
}
